 In this section, we study the problem of power assignment between multiple wireless links with various objectives. To solve the problem, we use the results from previous section as a local search method and combine it with simulated annealing as our generic method of choice for global search. Before we describe our algorithm, we formally define the problem and prove the following hardness results below.

\subsection{Hardness Results}

\textbf{Power Assignment Problem for $n$ links:} For any set of $n$ wireless nodes in a 2D plane, assign part a power signal to maximize one of objectives define in section \ref{sec:model}.

We prove the following theorems about power assignment problem.

\begin{theorem}
 \label{theo:power2}
    In the optimal solution of power assignment problem with proportional fairness or throughput as objectives, each sender should use its maximum power\footnote{Note that this is a weaker extension of theorem \ref{powertwolinks} to multiple links. In theorem \ref{powertwolinks}, we proved that the links use maximum power even when we restrict the power signal to a rectangle with just one center frequency. In this theorem however, we assume the links can use any arbitrary power signal.
}.
\end{theorem}

 \begin{theorem}
 \label{theo:hardness1}
    The power assignment problem for $n$ nodes is NP-hard with any of the objectives (proportional fairness,throughput and max-min).
 \end{theorem}
 
We differ the proofs to section \ref{sec:proofs}.

\subsection{Heuristic Algorithm}
 In this section, we combine the result of section \ref{sec:twoNodesConstantNoise} and a generic metaheuristic to come up with a heuristic algorithm to solve the class of problems discusses in the above section. Our metaheuristic of choice is simulated annealing(SA). Simulated Annealing is a well known metaheuristic by simulating the physical process used in shaping crystals. Each step of the SA algorithm attempts to replace the current solution by a random solution (chosen according to a candidate distribution, often constructed to sample from solutions near the current solution). The new solution may then be accepted with a probability that depends both on the difference between the corresponding function values and also on a global parameter T (called the temperature), that is gradually decreased during the process. The dependency is such that the choice between the previous and current solution is almost random when T is large, but increasingly selects the better or "downhill" solution (for a minimization problem) as T goes to zero.

In our algorithm, we again use discretization of the available bandwidth. Assume we break Bandwidth $B$ into $m$ channels and each link can use $1$ or more of these channels. $m$ would determine both precision and running time of our algorithm.

\subsection{SA Power Assignment Algorithm}

We combine simulated annealing with our local search as follows. While performing simulated annealing , during the he initialization step and after certain number of steps, we randomly select a set of pair of links. For each pair, we combine their used spectrum and then run the algorithm used in section \ref{sec:TwoLinksColoredNoise} for the nodes with interference from any other link is added to the noise levels. Finally, after finishing the simulated annealing, run the algorithm used in section \ref{sec:TwoLinksColoredNoise} for each pair of links. Note that however, running section \ref{sec:TwoLinksColoredNoise} algorithm sometime would result in lower overall capacity by increasing interference on other links. However, we hardly encountered such a scenario in our experiments. To account for this, we only apply the changes made by section \ref{sec:TwoLinksColoredNoise} algorithm if the overall capacity has been improved using this algorithm. Now, here is the formal definition of our algorithm.

\vspace{2mm}
\noindent\textbf{Algorithm Control Parameters:}
\vspace{2mm}

$T_init$ : The threshold to stop the initial solution improvement.

$T_fin$ : The threshold to stop the final search phase.

$G$: Step size in the global search.

$L$: Step size in local search.

$K$: neighboring parameters (the number of slots that could be added to the available spectrum of each link in one step).

$Temp_{init}$: The initial temperature of the system.

$I$: Total number of iterations.

\vspace{2mm}
\noindent\textbf{SA Algorithm for Max Throughput}
\begin{itemize}
\item  \textbf{Step 1: Initialization}

\begin{itemize}
\item  For each wireless link, randomly select an interval in the bandwidth as the transmitting channel, set the power level to maximum for all the links.

\item Compute $C$, the system throughput.

\item Sequentially, for each two links. Use section \ref{sec:TwoLinksColoredNoise} algorithm in the spectrum available to the links.

\item Randomly select two links. Use section \ref{sec:TwoLinksColoredNoise} algorithm in the spectrum available to the links. Compute $C$, the system total capacity. Apply the changes if $C$ has been improved. Repeat this step until the percentage of improvement in $C$ is below $T_{init}$ after 10 steps.
\end{itemize}

\item \textbf{Step 2: Search}

\begin{itemize}
\item set $temp=Temp_{init}$

\item  for $i=1$ to $G$ do as follows (Global Search Step).

\begin{itemize}
\item  Randomly select a wireless link. Randomly select up to $K$ bandwidth slots, where links is not transmitting in them, add them to the available spectrum of the link
\item Using ratio computed in lemma \ref{theo:DifferentNoise}; compute the optimum level of power for each bandwidth slots.
\item Compute $C$, the total throughput of the system.
\item If $C$ is better than the best global optimal, update the global optimal.
\item If $C$ is better than the previous computed throughput move to the new configuration, otherwise move to the new configuration if $random()<e^{-temp}$.
\end{itemize}

\item for $i=1$ to $L$ do as follows (Local Search Step).

\begin{itemize}
\item  Randomly select a pair of links. Use section \ref{sec:TwoLinksColoredNoise} algorithm on the two links in the spectrum available to the links. If either of the links stop transmitting in one of the slots, remove the slot from the link available spectrum.
\item Compute $C$. If $C$ is better than the best global optimal, update the global optimal.
\end{itemize}
\item temp= $temp\times(1.05)$;

\item If Counter is more than I then go to \emph{Finalize}, otherwise repeat \emph{step 2: Search}.
\end{itemize}
\end{itemize}
\begin{itemize}
\item \textbf{Finalize}
\begin{itemize}
\item  Select two links. Use section \ref{sec:TwoLinksColoredNoise} algorithm in the spectrum available to the links.  Repeat this step until the percentage of improvement in the capacity is below $T_fin$.
\end{itemize}
\end{itemize}

\vspace{1cm}
\subsubsection{SA Algorithm For Max Proportional Fairness and Max Min Throughput}
 In absence of algorithm for solving the two links case optimally, We use the pure simulated annealing for solving Max Proportional Fairness Channelization. We define the algorithm officially as follows.
 \vspace{2mm}
\noindent\textbf{Algorithm Control Parameters:}
We use the same control parameters as the previous section. Except in absence of local search, parameters $G$ and $L$ are omitted.
 \vspace{2mm}

\noindent\textbf{SA Max Fairness Spectrum Division Algorithm}
\begin{itemize}
\item  \textbf{Step 1: Initialization}

\begin{itemize}
\item  For each wireless link, randomly select an interval in the bandwidth as the transmitting channel, set the power level to maximum for all the links.

\item Compute $C$, the system proportional fairness measure and save it. Set it to the global optimal.
\end{itemize}

\item \textbf{Step 2: Search}

\begin{itemize}
\item set $temp=Temp_{init}$
\item  for $i=1$ to $I$ do as follows (Global Search Step).
\begin{itemize}
\item  Randomly select a wireless link. Randomly select up to $K$ bandwidth slots, where links is not transmitting in them, add them to the available spectrum of the link.
\item Using ratio computed in lemma \ref{theo:DifferentNoise}; compute the optimum level of power of the link for each bandwidth slots.
\item Compute $C$, the system proportional fairness measure.
\item if $C$ is better than global optimal, update the global optimal.
\item If $C$ is better than the previous computed throughput move to the new configuration, otherwise move to the new configuration if $random()<e^{-temp}$.
\item temp= $temp\times(1.0005)$;
\end{itemize}
\end{itemize}
\end{itemize}

